#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define MAX_LEN 120		//栈的最大容量
typedef char ElemType;	//数据的类型
typedef struct SqStack
{
	ElemType * data;//data指向一块地址连续的空间，来存储栈的每一个元素
	int top;//栈顶，指定栈顶元素的下标				// top == -1   表示栈中没有元素，空栈
}sq;

//初始化一个栈
sq *InitStack()		
{
	struct SqStack * s = malloc( sizeof(struct SqStack) );
	s->data = malloc(sizeof(ElemType) * MAX_LEN);	
	s->top = -1;					
	return s;
}
//判断是否为空栈
int IsEmpty(struct SqStack * s)
{
	//栈为空：栈不存在 || 栈里面没有元素
	if( s == NULL || s->top == -1 )
	{
		return 1;
	}
	return 0;
}

//判断栈满
int IsFull(sq *s)
{
	return (s->top==MAX_LEN-1);//从
}
//入栈 1成功 0失败
int Push(sq *s,ElemType d)
{
	if(IsFull(s)||s==NULL)
	{
		printf("Push error! \n");
		return 0;	
	}
	else
	{
		s->data[++s->top]=d;
		return 1;
	}
}
//出栈
int Pop(sq *s)
{
	if(IsEmpty(s)||s==NULL)
	{
		printf("Pop error! \n");
		return 0;
	}
	else
	{
		s->data[s->top--]=0;
		return 1;
	}
}
void CleanStack(sq	*s)
{
	memset(s->data,0,MAX_LEN);
	s->top=-1;
}
ElemType getTop(sq *s)
{
	return s->data[s->top];
}
void match(sq *s)
{
	ElemType str[MAX_LEN];
	int i,str_len,flag=1;
	fgets(str,MAX_LEN,stdin);
	str_len=strlen(str);
	//printf("{len:%d}\n",str_len);
	for(i=0;i<str_len;i++)
	{
		if(str[i]=='{'||str[i]=='['||str[i]=='(')
		{
			Push(s, str[i]);
			//printf("===str[%d]:%c===\n",i,str[i]);
		}
		else if(str[i]=='}'||str[i]==']'||str[i]==')')
		{
			ElemType x=getTop(s);
			//printf("x:%c  str[%d]:%c\n",x,i,str[i]);
			if(x=='{'&&str[i]=='}' || x=='['&& str[i]==']' || x=='('&&str[i]==')')
			{
				Pop(s);
			}
			else
			{
				flag=0;
				break;
			}
		}
	}
	if(flag==0)
	{
		printf("no matching!\n");
	}
	else if(flag==1&&IsEmpty(s))
	{
		printf("matching!\n");
	}
}

//[26*(12+8)/(45-29)]
//[26*(12+8)/(45-29)]}
int main()
{
	sq *s=InitStack();
	match(s);
	
	return 0;
}

